package leetcode.editor.day;

// 998. 最大二叉树 II
// https://leetcode.cn/problems/maximum-binary-tree-ii/
class MaximumBinaryTreeIi {
    public static void main(String[] args) {
        Solution solution = new MaximumBinaryTreeIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // https://leetcode.cn/problems/maximum-binary-tree-ii/solution/zui-da-er-cha-shu-er-by-capital-worker-txa0/
    class Solution {
        // dfs
        /*public TreeNode insertIntoMaxTree(TreeNode root, int val) {
            return dfs(root, val);
        }

        public TreeNode dfs(TreeNode root, int val) {
            if (root == null) return new TreeNode(val);

            if (root.val < val) {
                TreeNode node = new TreeNode(val);
                node.left = root;
                return node;
            }

            // 只递归右子树，因为是从末尾加入，一定在右子树
            // 由于新的数字b是加到了数组的末尾，因此b所代表的的节点要么是插在原二叉树的右子树里面 ，要么作为总的根节点
            root.right = dfs(root.right, val);

            return root;
        }*/

        // BFS
        // https://leetcode.cn/problems/maximum-binary-tree-ii/solution/zui-da-er-cha-shu-ii-by-leetcode-solutio-piv2/
        public TreeNode insertIntoMaxTree(TreeNode root, int val) {
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null) {
                if (cur.val < val) {
                    TreeNode node = new TreeNode(val);
                    // 第一个元素，直接返回
                    if (parent == null) {
                        node.left = root;
                        return node;
                    } else {
                        node.left = cur;
                        parent.right = node;
                        return root;
                    }
                } else {
                    parent = cur;
                    cur = cur.right;
                }
            }

            // 最后一个节点
            parent.right = new TreeNode(val);

            return root;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
